package com.arron.algorithm.leetcodetop100.链表;


import com.arron.algorithm.leetcodetop100.ListNode;

import java.util.List;

/**
 *
 *  leetcode 234. 回文链表
 */
public class 回文链表 {


    /**
     * 判断是否是回文链表
     *  解法一：使用数组来存链表中的值，然后双指针遍历判断
     *      会产生额外空间
     * @param head
     * @return
     */
    public boolean isPalindrome1(ListNode head) {

        if (head == null) return false;
        ListNode p1 = head;

        int listLength=0,i = 0;
        while (p1!=null){
            p1 = p1.next;
            listLength++;
        }
        int[] array = new int[listLength];
        p1 = head;
        while (p1!=null){
            array[i] = p1.val;
            p1 = p1.next;
            i++;
        }
        boolean flag = true;
        for (int k =0 ,j= array.length-1; k <= array.length/2 && j>= array.length/2; k++,j--) {
            if (array[k] != array[j]){
                flag = false;
                break;
            }
        }
        return flag;
    }

    /**
     * 解法二：不产生额外空间
     *  使用截断链表，并反转链表进行判断
     *
     * @param head
     * @return
     */
    public boolean isPalindrome2(ListNode head) {

        if (head == null) return false;
        //使用快慢指针找到截断点
        ListNode slowNode = head;
        ListNode fastNode = head;
        while (fastNode !=null && fastNode.next!=null){
            slowNode = slowNode.next;
            fastNode = fastNode.next.next;
        }

        if (fastNode!=null){
            //奇数个节点就将慢节点归到另一边
            slowNode = slowNode.next;
        }

        slowNode = reverseNode(slowNode);
        fastNode = head;
        boolean flag = true;
        while (slowNode!=null){
            if (fastNode.val != slowNode.val){
                flag = false;
                break;
            }
            slowNode = slowNode.next;
            fastNode = fastNode.next;
        }

        return flag;
    }

    /**
     * 反转链表
     * @param slowNode
     * @return
     */
    private ListNode reverseNode(ListNode slowNode) {

        if (slowNode == null || slowNode.next == null) return slowNode;

        ListNode temp = null;
        ListNode pre = null;
        ListNode cur = slowNode;

        while (cur!=null){
            temp = cur.next;
            cur.next = pre;
            pre = cur;
            cur = temp;
        }
        return pre;
    }


}
